// public class Solution {
//     /*
//         思路1：快慢指针
//         注意点：
//                1. if (head == null || head.next == null) {
//                         return false;
//                     }
//                2. 如果相交，那么p1,p2一定会相交。
//                   如果不想交，那么p2一定先变为null
//         空间复杂度：O（1）
//     */
//     public boolean hasCycle(ListNode head) {
//         if (head == null || head.next == null) {
//             return false;
//         }
//         ListNode p1 = head, p2 = head.next;
//         while(p1 != p2){
//             // System.out.println(p1+" "+p2);
//             if(p2==null || p2.next==null)
//                 return false;
//             p1 = p1.next;
//             p2 = p2.next.next;
//         }
//         return true;
//     }
// }
public class Solution {
    /*
        思路1：快慢指针
    */
    public boolean hasCycle(ListNode head) {
        ListNode low = head,fast = head;
        /*
            退出条件：
                存在环：  low == fast != null
                不存在环：fast == null, low != null;
        */
        while( fast!=null && fast.next!=null ){
            low = low.next;
            fast = fast.next.next;
            if(low == fast)
                return true;
        }
        return false;
    }
}
public class Solution {
    /*
        思路2：哈希表
        空间复杂度：O(N)，即为哈希表的节点数
    */
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while(head!=null){
            if(set.contains(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }
}